<!DOCTYPE html>
<html lang="en" class="no-js">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width,initial-scale=1">
<meta http-equiv="x-ua-compatible" content="ie=edge">
<meta name="description" content="PragmaticScala">
<meta name="generator" content="Paradox, paradox-material-theme=0.5.1, mkdocs-material=3.0.3">

<meta name="lang:clipboard.copy" content="Copy to clipboard">
<meta name="lang:clipboard.copied" content="Copied to clipboard">
<meta name="lang:search.language" content="">
<meta name="lang:search.pipeline.stopwords" content="true">
<meta name="lang:search.pipeline.trimmer" content="true">
<meta name="lang:search.result.none" content="No matching documents">
<meta name="lang:search.result.one" content="1 matching document">
<meta name="lang:search.result.other" content="# matching documents">
<meta name="lang:search.tokenizer" content="[\s\-]+">


<meta name="description" content="PragmaticScala">
<link rel="shortcut icon" href="../assets/images/favicon.png">
<title>第11章——递归编程 · </title>
<link rel="stylesheet" href="../assets/stylesheets/application.451f80e5.css">
<link rel="stylesheet" href="../lib/material__tabs/dist/mdc.tabs.min.css">
<link rel="stylesheet" href="../lib/prettify/prettify.css">
<script src="../assets/javascripts/modernizr.1aa3b519.js"></script>
<link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Roboto:300,400,400i,700|Roboto+Mono">
<style>
body,input{font-family:"Roboto","Helvetica Neue",Helvetica,Arial,sans-serif}
code,kbd,pre{font-family:"Roboto Mono","Courier New",Courier,monospace}
</style>
<link rel="stylesheet" href="../assets/fonts/font-awesome.css">
<link rel="stylesheet" href="../assets/fonts/material-icons.css">
<link rel="stylesheet" href="../assets/stylesheets/paradox-material-theme.css">
</head>
<body
>
<input class="md-toggle" data-md-toggle="drawer" type="checkbox" id="__drawer" autocomplete="off">
<input class="md-toggle" data-md-toggle="search" type="checkbox" id="__search" autocomplete="off">
<label class="md-overlay" data-md-component="overlay" for="__drawer"></label>
<header class="md-header" data-md-component="header">
<nav class="md-header-nav md-grid">
<div class="md-flex">
<div class="md-flex__cell md-flex__cell--shrink">
<a href="../index.html" title="" class="md-header-nav__button md-logo">
<i class="md-icon">local_library</i>
</a>
</div>
<div class="md-flex__cell md-flex__cell--shrink">
<label class="md-icon md-icon--menu md-header-nav__button" for="__drawer"></label>
</div>
<div class="md-flex__cell md-flex__cell--stretch">
<div class="md-flex__ellipsis md-header-nav__title" data-md-component="title">
<span class="md-header-nav__topic">
</span>
<span class="md-header-nav__topic">
第11章——递归编程
</span>
</div>
</div>
<div class="md-flex__cell md-flex__cell--shrink">
<label class="md-icon md-icon--search md-header-nav__button" for="__search"></label>
<div class="md-search" data-md-component="search" role="dialog">
<label class="md-search__overlay" for="__search"></label>
<div class="md-search__inner" role="search">
<form class="md-search__form" name="search">
<input type="text" class="md-search__input" name="query" placeholder="Search" autocapitalize="off" autocorrect="off" autocomplete="off" spellcheck="false" data-md-component="query" data-md-state="active">
<label class="md-icon md-search__icon" for="__search"></label>
<button type="reset" class="md-icon md-search__icon" data-md-component="reset" tabindex="-1">&#xE5CD;</button>
</form>
<div class="md-search__output">
<div class="md-search__scrollwrap" data-md-scrollfix>
<div class="md-search-result" data-md-component="result">
<div class="md-search-result__meta">
Type to start searching
</div>
<ol class="md-search-result__list"></ol>
</div>
</div>
</div>
</div>
</div>

</div>
</div>
</nav>
</header>

<div class="md-container">
<main class="md-main">
<div class="md-main__inner md-grid" data-md-component="container">
<div class="md-sidebar md-sidebar--primary" data-md-component="navigation">
<div class="md-sidebar__scrollwrap">
<div class="md-sidebar__inner">
<nav class="md-nav md-nav--primary" data-md-level="0" style="visibility: hidden">
<label class="md-nav__title md-nav__title--site" for="drawer">
<a href="../index.html" title="" class="md-nav__button md-logo">
<span class="md-nav__button md-logo">
<i class="md-icon">local_library</i>
</a>
<a href="../index.html" title="">
</a>
</label>
<ul>
  <li><a href="../contents.html" class="page">目录</a>
  <ul>
    <li><a href="../abstract.html" class="page">内容提要</a></li>
    <li><a href="../part1.html" class="page">第一部分 小试牛刀</a></li>
    <li><a href="../part2.html" class="page">第二部分 深入 Scala</a></li>
    <li><a href="../part3.html" class="page">第三部分 Scala 中的并发编程</a></li>
    <li><a href="../part4.html" class="page">第四部分 Scala 实战</a></li>
    <li><a href="../refs/references.html" class="page">参考书目</a></li>
    <li><a href="../extras.html" class="page">额外指引</a></li>
    <li><a href="../errata.html" class="page">勘误</a></li>
  </ul></li>
</ul>
<nav class="md-nav md-nav--secondary">
<label class="md-nav__title" for="__toc">Table of contents</label>
<ul>
  <li><a href="../chapter-11/index.html#第11章-递归编程" class="header">第11章——递归编程</a>
  <ul>
    <li><a href="../chapter-11/index.html#11-1-一个简单的递归" class="header">11.1 一个简单的递归</a></li>
    <li><a href="../chapter-11/index.html#11-2-尾调用优化-tco-" class="header">11.2 尾调用优化（TCO）</a></li>
    <li><a href="../chapter-11/index.html#11-3-蹦床调用" class="header">11.3 蹦床调用</a></li>
  </ul></li>
</ul>
</nav>

</nav>
<ul style="display: none">
<li class="md-nav__item md-version" id="project.version">
<label class="md-nav__link" for="__version">
<i class="md-icon" title="Version">label_outline</i> 1.0.0
</label>
</li>
</ul>
</div>
</div>
</div>
<div class="md-sidebar md-sidebar--secondary" data-md-component="toc">
<div class="md-sidebar__scrollwrap">
<div class="md-sidebar__inner">
<nav class="md-nav md-nav--secondary">
<label class="md-nav__title" for="__toc">Table of contents</label>
<ul>
  <li><a href="../chapter-11/index.html#第11章-递归编程" class="header">第11章——递归编程</a>
  <ul>
    <li><a href="../chapter-11/index.html#11-1-一个简单的递归" class="header">11.1 一个简单的递归</a></li>
    <li><a href="../chapter-11/index.html#11-2-尾调用优化-tco-" class="header">11.2 尾调用优化（TCO）</a></li>
    <li><a href="../chapter-11/index.html#11-3-蹦床调用" class="header">11.3 蹦床调用</a></li>
  </ul></li>
</ul>
</nav>

</div>
</div>
</div>
<div class="md-content">
<article class="md-content__inner md-typeset">
<div class="md-content__searchable">
<h1><a href="#第11章-递归编程" name="第11章-递归编程" class="anchor"><span class="anchor-link"></span></a>第11章——递归编程</h1>
<p>使用解决子问题的方案解决一个问题，也就是递归，这种想法十分诱人。许多算法和 问题本质上都是递归的。一旦我们找到窍门，使用递归来设计解决方案就变得极富表现力 且直观。</p>
<h2><a href="#11-1-一个简单的递归" name="11-1-一个简单的递归" class="anchor"><span class="anchor-link"></span></a>11.1 一个简单的递归</h2>
<blockquote>
  <p>ProgrammingRecursions/Factorial.scala</p>
</blockquote>
<pre class="prettyprint"><code class="language-scala">def factorial(number: Int): BigInt = {
  if (number == 0)
    1
  else
    number * factorial(number - 1)
}</code></pre><a href="https://github.com/ReactivePlatform/Pragmatic-Scala.git/tree/v1.0.0/src/main/scala/chapter11/Factorial.scala#L21-L26">Full source at GitHub</a>
<p><em>运行结果</em></p>
<pre class="prettyprint"><code class="language-output">120</code></pre><a href="https://github.com/ReactivePlatform/Pragmatic-Scala.git/tree/v1.0.0/src/main/scala/chapter11/output/factorial.output#L2">Full source at GitHub</a>
<blockquote>
  <p>ProgrammingRecursions/Factorial.scala</p>
</blockquote>
<pre class="prettyprint"><code class="language-scala">println(factorial(5))</code></pre><a href="https://github.com/ReactivePlatform/Pragmatic-Scala.git/tree/v1.0.0/src/main/scala/chapter11/Factorial.scala#L30">Full source at GitHub</a>
<blockquote>
  <p>ProgrammingRecursions/Factorial.scala</p>
</blockquote>
<pre class="prettyprint"><code class="language-scala">println(factorial(10000))</code></pre><a href="https://github.com/ReactivePlatform/Pragmatic-Scala.git/tree/v1.0.0/src/main/scala/chapter11/Factorial.scala#L35">Full source at GitHub</a>
<p><em>运行结果</em></p>
<pre class="prettyprint"><code class="language-output">java.lang.StackOverflowError</code></pre><a href="https://github.com/ReactivePlatform/Pragmatic-Scala.git/tree/v1.0.0/src/main/scala/chapter11/output/factorial.output#L6">Full source at GitHub</a>
<h2><a href="#11-2-尾调用优化-tco-" name="11-2-尾调用优化-tco-" class="anchor"><span class="anchor-link"></span></a>11.2 尾调用优化（TCO）</h2>
<blockquote>
  <p>ProgrammingRecursions/Mad.scala</p>
</blockquote>
<pre class="prettyprint"><code class="language-scala">def mad(parameter: Int): Int = {
  if (parameter == 0)
    throw new RuntimeException(&quot;Error&quot;)
  else
    1 * mad(parameter - 1)
}

mad(5)</code></pre><a href="https://github.com/ReactivePlatform/Pragmatic-Scala.git/tree/v1.0.0/src/main/scala/chapter11/Mad.scala#L21-L28">Full source at GitHub</a>
<p><em>运行结果</em></p>
<pre class="prettyprint"><code class="language-output">java.lang.RuntimeException: Error
	at Main$$anon$1.mad(mad.scala:3)
	at Main$$anon$1.mad(mad.scala:5)
	at Main$$anon$1.mad(mad.scala:5)
	at Main$$anon$1.mad(mad.scala:5)
	at Main$$anon$1.mad(mad.scala:5)
	at Main$$anon$1.mad(mad.scala:5)
	at Main$$anon$1.&lt;init&gt;(mad.scala:8)</code></pre><a href="https://github.com/ReactivePlatform/Pragmatic-Scala.git/tree/v1.0.0/src/main/scala/chapter11/shoutput/RunMad.output#L2-L9">Full source at GitHub</a>
<blockquote>
  <p>ProgrammingRecursions/Mad2.scala</p>
</blockquote>
<pre class="prettyprint"><code class="language-scala">def mad(parameter: Int): Int = {
  if (parameter == 0)
    throw new RuntimeException(&quot;Error&quot;)
  else
    mad(parameter - 1)
}

mad(5)</code></pre><a href="https://github.com/ReactivePlatform/Pragmatic-Scala.git/tree/v1.0.0/src/main/scala/chapter11/Mad2.scala#L21-L28">Full source at GitHub</a>
<p><em>运行结果</em></p>
<pre class="prettyprint"><code class="language-output">java.lang.RuntimeException: Error
	at Main$$anon$1.mad(mad2.scala:3)
	at Main$$anon$1.&lt;init&gt;(mad2.scala:8)</code></pre><a href="https://github.com/ReactivePlatform/Pragmatic-Scala.git/tree/v1.0.0/src/main/scala/chapter11/shoutput/RunMad2.output#L2-L4">Full source at GitHub</a>
<pre class="prettyprint"><code class="language-output">  private int mad(int);
    Code:
       0: iload_1
       1: iconst_0
       2: if_icmpne     15
       5: new           #14                 // class 
java/lang/RuntimeException
       8: dup
       9: ldc           #16                 // String Error
      11: invokespecial #20                 // Method 
java/lang/RuntimeException.&quot;&lt;init&gt;&quot;:(Ljava/lang/String;)V
      14: athrow
      15: iconst_1
      16: aload_0
      17: iload_1
      18: iconst_1
      19: isub
      20: invokespecial #22                 // Method mad:(I)I
      23: imul
      24: ireturn</code></pre><a href="https://github.com/ReactivePlatform/Pragmatic-Scala.git/tree/v1.0.0/src/main/scala/chapter11/shoutput/ViewJar1.output#L2-L21">Full source at GitHub</a>
<pre class="prettyprint"><code class="language-output">  private int mad(int);
    Code:
       0: iload_1
       1: iconst_0
       2: if_icmpne     15
       5: new           #14                 // class 
java/lang/RuntimeException
       8: dup
       9: ldc           #16                 // String Error
      11: invokespecial #20                 // Method 
java/lang/RuntimeException.&quot;&lt;init&gt;&quot;:(Ljava/lang/String;)V
      14: athrow
      15: iload_1
      16: iconst_1
      17: isub
      18: istore_1
      19: goto          0</code></pre><a href="https://github.com/ReactivePlatform/Pragmatic-Scala.git/tree/v1.0.0/src/main/scala/chapter11/shoutput/ViewJar2.output#L2-L18">Full source at GitHub</a>
<blockquote>
  <p>ProgrammingRecursions/FactorialNoTCO.scala</p>
</blockquote>
<pre class="prettyprint"><code class="language-scala">@scala.annotation.tailrec
def factorial(number: Int): BigInt = {
  if (number == 0)
    1
  else
    number * factorial(number - 1)
}

println(factorial(10000))</code></pre><a href="https://github.com/ReactivePlatform/Pragmatic-Scala.git/tree/v1.0.0/src/test/scala/chapter11/FactorialNoTCO.scala#L21-L29">Full source at GitHub</a>
<p><em>运行结果</em></p>
<pre class="prettyprint"><code class="language-output">error: could not optimize @tailrec annotated method factorial: it contains
a recursive call not in tail position
    number * factorial(number - 1)
           ^
error found</code></pre><a href="https://github.com/ReactivePlatform/Pragmatic-Scala.git/tree/v1.0.0/src/main/scala/chapter11/shoutput/RunFactorialNoTCO.output#L2-L6">Full source at GitHub</a>
<blockquote>
  <p>ProgrammingRecursions/FactorialTCO.scala</p>
</blockquote>
<pre class="prettyprint"><code class="language-scala">@scala.annotation.tailrec
def factorial(fact: BigInt, number: Int): BigInt = {
  if (number == 0)
    fact
  else
    factorial(fact * number, number - 1)
}

println(factorial(1, 10000))</code></pre><a href="https://github.com/ReactivePlatform/Pragmatic-Scala.git/tree/v1.0.0/src/main/scala/chapter11/FactorialTCO.scala#L21-L29">Full source at GitHub</a>
<p><em>运行结果</em></p>
<pre class="prettyprint"><code class="language-output">284625968091705451890641321211986889014805140170279923079417999427441134000
...</code></pre><a href="https://github.com/ReactivePlatform/Pragmatic-Scala.git/tree/v1.0.0/src/main/scala/chapter11/shoutput/RunFactorialTCO.output#L2-L3">Full source at GitHub</a>
<h2><a href="#11-3-蹦床调用" name="11-3-蹦床调用" class="anchor"><span class="anchor-link"></span></a>11.3 蹦床调用</h2>
<blockquote>
  <p>ProgrammingRecursions/Words.scala</p>
</blockquote>
<pre class="prettyprint"><code class="language-scala">import scala.io.Source._

def explore(count: Int, words: List[String]): Int =
  if (words.isEmpty)
    count
  else
    countPalindrome(count, words)

def countPalindrome(count: Int, words: List[String]): Int = {
  val firstWord = words.head

  if (firstWord.reverse == firstWord)
    explore(count + 1, words.tail)
  else
    explore(count, words.tail)
}

def callExplore(text: String): Unit = println(explore(0, text.split(&quot; &quot;).toList))

callExplore(&quot;dad mom and racecar&quot;)

try {
  val text =
    fromURL(&quot;https://en.wikipedia.org/wiki/Gettysburg_Address&quot;).mkString
  callExplore(text)
} catch {
  case ex: Throwable ⇒ println(ex)
}</code></pre><a href="https://github.com/ReactivePlatform/Pragmatic-Scala.git/tree/v1.0.0/src/main/scala/chapter11/Words.scala#L22-L49">Full source at GitHub</a>
<p><em>运行结果</em></p>
<pre class="prettyprint"><code class="language-output">3
java.lang.StackOverflowError</code></pre><a href="https://github.com/ReactivePlatform/Pragmatic-Scala.git/tree/v1.0.0/src/main/scala/chapter11/output/words.output#L2-L3">Full source at GitHub</a>
<blockquote>
  <p>ProgrammingRecursions/WordsTrampoline.scala</p>
</blockquote>
<pre class="prettyprint"><code class="language-scala">import scala.io.Source._
import scala.util.control.TailCalls._

def explore(count: Int, words: List[String]): TailRec[Int] =
  if (words.isEmpty)
    done(count)
  else
    tailcall(countPalindrome(count, words))

def countPalindrome(count: Int, words: List[String]): TailRec[Int] = {
  val firstWord = words.head

  if (firstWord.reverse == firstWord)
    tailcall(explore(count + 1, words.tail))
  else
    tailcall(explore(count, words.tail))
}

def callExplore(text: String): Unit =
  println(explore(0, text.split(&quot; &quot;).toList).result)

callExplore(&quot;dad mom and racecar&quot;)

try {
  val text =
    fromURL(&quot;https://en.wikipedia.org/wiki/Gettysburg_Address&quot;).mkString
  callExplore(text)
} catch {
  case ex: Throwable ⇒ println(ex)
}</code></pre><a href="https://github.com/ReactivePlatform/Pragmatic-Scala.git/tree/v1.0.0/src/main/scala/chapter11/WordsTrampoline.scala#L21-L50">Full source at GitHub</a>
<p><em>运行结果</em></p>
<pre class="prettyprint"><code class="language-output">3
352</code></pre><a href="https://github.com/ReactivePlatform/Pragmatic-Scala.git/tree/v1.0.0/src/main/scala/chapter11/output/wordsTrampoline.output#L2-L3">Full source at GitHub</a>
</div>
<div>
<a href="https://github.com/ReactivePlatform/Pragmatic-Scala.git/tree/master/src/paradox/chapter-11/index.md" title="Edit this page" class="md-source-file md-edit">
Edit this page
</a>
</div>
<div class="print-only">
<span class="md-source-file md-version">
1.0.0
</span>
</div>
</article>
</div>
</div>
</main>
<footer class="md-footer">
<div class="md-footer-nav">
<nav class="md-footer-nav__inner md-grid">
<a href="../chapter-10/index.html" title="第10章——处理异常" class="md-flex md-footer-nav__link md-footer-nav__link--prev" rel="prev">
<div class="md-flex__cell md-flex__cell--shrink">
<i class="md-icon md-icon--arrow-back md-footer-nav__button"></i>
</div>
<div class="md-flex__cell md-flex__cell--stretch md-footer-nav__title">
<span class="md-flex__ellipsis">
<span class="md-footer-nav__direction">
Previous
</span>
第10章——处理异常
</span>
</div>
</a>
<a href="../part3.html" title="第三部分 Scala 中的并发编程" class="md-flex md-footer-nav__link md-footer-nav__link--next" rel="next">
<div class="md-flex__cell md-flex__cell--stretch md-footer-nav__title">
<span class="md-flex__ellipsis">
<span class="md-footer-nav__direction">
Next
</span>
第三部分 Scala 中的并发编程
</span>
</div>
<div class="md-flex__cell md-flex__cell--shrink">
<i class="md-icon md-icon--arrow-forward md-footer-nav__button"></i>
</div>
</a>
</nav>
</div>
<div class="md-footer-meta md-typeset">
<div class="md-footer-meta__inner md-grid">
<div class="md-footer-copyright">
Powered by
<a href="https://github.com/lightbend/paradox">Paradox</a>
and
<a href="https://jonas.github.io/paradox-material-theme/">Paradox Material Theme</a>

</div>
</div>
</div>
</footer>

</div>
<script src="../assets/javascripts/application.583bbe55.js"></script>
<script src="../assets/javascripts/paradox-material-theme.js"></script>
<script>app.initialize({version:"0.17",url:{base:"../."}})</script>
<script type="text/javascript" src="../lib/prettify/prettify.js"></script>
<script type="text/javascript" src="../lib/prettify/lang-scala.js"></script>
<script type="text/javascript">
document.addEventListener("DOMContentLoaded", function(event) {
window.prettyPrint && prettyPrint();
});
</script>
</body>
</html>
